package likou;

import java.util.*;

public class _446 {
    public static void main(String[] args) {
        System.out.println(numberOfArithmeticSlices2(new int[]{
                7, 7, 7, 7, 7
        }));
    }

    static Map<Integer, Set<Integer>> setMap = new HashMap<>();

    public static int numberOfArithmeticSlices(int[] nums) {
        int res = 0;
        int len = nums.length;
        Map<Integer, ArrayList<Integer>> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            if (map.containsKey(nums[i])) {
                map.get(nums[i]).add(i);
            } else {
                int finalI = i;
                map.put(nums[i], new ArrayList<Integer>() {{
                    add(finalI);
                }});
            }
        }
        setMap.put(0, new HashSet<>());
        for (int i = 0; i < len - 2; i++) {
            for (int j = i + 1; j < len - 1; j++) {
                int dep = nums[i] - nums[j];
                if (dep == 0 && !setMap.get(dep).contains(nums[i])) {
                    res += getRes(map.get(nums[i]).size());
                    setMap.get(0).add(nums[i]);
                    continue;
                } else if (setMap.containsKey(dep)) {
                    if (setMap.get(dep).contains(nums[j]))
                        continue;
                    setMap.get(dep).add(nums[i]);
                    setMap.get(dep).add(nums[j]);
                } else if (!setMap.containsKey(dep)) {
                    int finalI = i;
                    int finalJ = j;
                    HashSet<Integer> set = new HashSet<Integer>() {{
                        add(nums[finalI]);
                        add(nums[finalJ]);
                    }};
                    setMap.put(dep, set);
                }
                res += dfs(nums, map, 2, j, nums[i] - nums[j]);
            }
        }
        return res;
    }

    /**
     * @param nums
     * @param map
     * @param nowsize 当前的长度
     * @param lastI   上一位的位置
     * @param dep     等差数
     * @return
     */
    public static int dfs(int[] nums, Map<Integer, ArrayList<Integer>> map, int nowsize, int lastI, int dep) {
        ArrayList<Integer> list = map.get(nums[lastI] - dep);
        if (list == null || list.size() == 0 || list.get(list.size() - 1) < lastI) {
            return getRes(nowsize);
        } else {
            setMap.get(dep).add(nums[lastI] - dep);
            int i = 0;
            for (; i < list.size(); i++) {
                if (list.get(i) > lastI) break;
            }
            i = list.size() - i;
            return i * dfs(nums, map, nowsize + 1, list.get(list.size() - 1), dep);
        }
    }

    public static int getRes(int nowsize) {
        return (nowsize - 2) * (nowsize - 1) / 2;
    }


    public static int numberOfArithmeticSlices2(int[] nums) {
        int ans = 0;
        int n = nums.length;
        Map<Long, Integer>[] map = new Map[n];
        for (int i = 0; i < n; i++) {
            map[i] = new HashMap<>();
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                long d = 1L * nums[i] - nums[j];
                int cnt = map[j].getOrDefault(d, 0);
                ans += cnt;
                map[i].put(d, map[i].getOrDefault(d, 0) + cnt + 1);
            }
        }
        return ans;
    }

    public int numberOfArithmeticSlices3(int[] nums) {
        int res = 0;
        int len = nums.length;
        //key:当前位置与前面所有位置值的差值; value:出现当前差值key的个数
        Map<Long, Integer>[] maps = new Map[len];
        Arrays.fill(maps, new HashMap<>());
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                long cha = (long) nums[i] - nums[j];
                // cnt：当前j之前和j的差值为 cha的元素个数
                int cnt = maps[j].getOrDefault(cha, 0);
                res += cnt;
                maps[i].merge(cha, 1 + cnt, Integer::sum);
            }
        }
        return res;

        /* maps[i]的 key:公差; value:出现当前差值key的个数
         * 比如: 1,2,3: 当前下标为1，maps[1]里面存的是 key:1,value:1(有一个2-1为1)
         *             当前下标为2，maps[2]里面存的是 key:1,value:1(有一个3-2为1),key:2,value:1 (有一个3-1为2)
         *     此时如果下标为2，则res += 下标为2之前的全部公差为1的value
         *     即：res += maps[0].getOrDefault(1,0) + maps[1].getOrDefault(1,0);
         *        res += 0 + 1;
         *
         * 比如: 1,2,3,4
         *     当前下标为3，
         *   i=0  cnt=0                          res+=cnt(0)         maps[0]->空
         *   i=1  cnt=0                          res+=cnt(0)         maps[1] -> key:1,value:1;
         *   i=2  cnt=maps[1].getOrDefault(1,0)  res+=cnt(1)         maps[2] -> key:1,value:1; key:2,value:1;
         *   i=3  cnt=maps[1].getOrDefault(1,0)
         *        cnt=maps[2].getOrDefault(1,0)  res+=cnt(1)+cnt(1)  maps[3] -> key:1,value:1; key:2,value:1; key:3,value:1
         *
         *    上面的cnt，只写了差值为1的情况，即getOrDefault(1,0)；其实还有getOrDefault(2,0)：2为3-1或4-2情况下。但是这个2并不能产生等差数列，所以我没写出来。
         */
    }

}
